软考真题
首页
题库
登录
第72题
【说明】
计算两个字符串x和y的最长公共子串(Longest Common Substring)。
假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。
c[i][j]满足最优子结构,其递归定义为:
计算所有c[i][j](0≤i≤m,0≤j≤n)的值,值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j,确定一个最长公共子串。
(1) 常量和变量说明
x,y:长度分别为m和n的字符串。
c[i][j]:记录x中前i字符和y中前j个字符的最长公共子串的长度。
max:x和y的最长公共子串的长度。
maxi,maxj:分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置(序号)。
(2) C程序
【问题:4.1】根据以上说明和C代码,填充C代码中的空(1)~(4)。
【问题:4.2】根据题干说明和以上C代码,算法采用了(5)设计策略。
分析时间复杂度为(6)(用O符号表示)。
【问题:4.3】根据题干说明和以上C代码,输入字符串x="ABCADAB’,'y="BDCABA",则输出为(7)。
第2章 程序设计语言基础知识
正确答案:
你的答案:
上一题
下一题
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2015年 下半年 下午试卷 案例
标签:
计算所
递归
常量
字符串
ABC
函数
算法
动态规划
结构
动态规划方法
数组
CAD
时间复杂度
复杂度
复杂度分析
最大值
符号表
子串
CAB
语言
算法设计
笔记
提交
请先在App中激活(应用市场搜“软考真题”)
2019-10-26
5
请先在App中激活(应用市场搜“软考真题”)
2019-10-12
4
请先在App中激活(应用市场搜“软考真题”)
2019-10-27
2
请先在App中激活(应用市场搜“软考真题”)
2019-11-06
1
失之定归
请先在App中激活(应用市场搜“软考真题”)
2020-04-18
1
李建雄
请先在App中激活(应用市场搜“软考真题”)
2020-10-29
1
答题卡
加油
计算器
纠错
草稿纸
得分:0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151